#include <bits/stdc++.h>
#include <unistd.h>

using namespace std;

// 有效涂色问题
// 给定n、m两个参数
// 一共有n个格子，每个格子可以涂上一种颜色，颜色在m种里选
// 当涂满n个格子，并且m种颜色都使用了，叫一种有效方法
// 求一共有多少种有效的涂色方法
// 1 <= n, m <= 5000
// 结果比较大请 % 1000000007 之后返回
// 对数器验证

// 把所有填色的方法暴力枚举
// 然后一个一个验证是否有效
// 这是一个带路径的递归
// 无法改成动态规划
int f(vector<int>& path, vector<bool>& visited, int i, int n, int m)
{
    if(i == n)
    {
        fill(visited.begin(), visited.end(), false);
        // 检查 n 个格子涂满时，是否 m 种颜色都使用了
        int colors = 0; // 使用过的颜色总是
        for(int c : path)
        {
            // 记录 c 这种颜色使用过
            if(!visited[c])
            {
                visited[c] = true;
                ++colors;
            }
        }
        return colors == m ? 1 : 0;
    }
    else
    {
        int ans = 0;
        for(int j = 1; j <= m; ++j)
        {
            path[i] = j; // 第 i 个格子放 j 颜色
            ans += f(path, visited, i + 1, n, m);
        }
        return ans;
    }
}

// 暴力方法
// 为了验证
int ways1(int n, int m)
{
    vector<int> path(n);
    vector<bool> visited(m + 1);
    return f(path, visited, 0, n, m);
}

// 正式方法
// 时间复杂度O(n * m)
// 已经展示太多次从递归到动态规划了
// 直接写动态规划吧
const int MAXN = 5001;
const int MOD = 1e9 + 7;
int dp[MAXN][MAXN];

int ways2(int n, int m)
{
    // dp[i][j] : 一共有j种颜色，前i个格子涂满j种颜色的方法数
    for(int i = 1; i <= n; ++i) dp[i][1] = m;
    for(int i = 2; i <= n; ++i)
    {
        for(int j = 2; j <= m; ++j)
        {
            // 给第 i 个格子涂上之前已经出现过的颜色
            dp[i][j] = ((long)dp[i - 1][j] * j) % MOD;
            // 给第 i 个格子涂上之前没有出现过的颜色
            dp[i][j] = ((long)dp[i - 1][j - 1] * (m - j + 1) + dp[i][j]) % MOD;
        }
    }

    return dp[n][m];
}

// 空间压缩
int ways3(int n, int m)
{
    int f[m + 1];
    memset(f, 0, sizeof f);
    f[1] = m;
    for(int i = 2; i <= n; ++i)
    {
        for(int j = 2, leftUp = m, backup; j <= m; ++j)
        {
            backup = f[j];
            f[j] = ((long)f[j] * j) % MOD;
            f[j] = ((long)leftUp * (m - j + 1) + f[j]) % MOD;
            leftUp = backup;
        }
    }
    return f[m];
}

int main()
{
    // 测试的数据量比较小
    // 那是因为数据量大了，暴力方法过不了
    // 但是这个数据量足够说明正式方法是正确的
    int N = 9, M = 9;
    cout << "功能测试开始" << endl;
    for(int n = 1; n <= N; ++n)
    {
        for(int m = 1; m <= M; ++m)
        {
            int ans1 = ways2(n, m);
            int ans2 = ways3(n, m);
            if(ans1 != ans2)
            {
                cout << "出错了!" << endl;
            }
        }
    }
    cout << "功能测试结束" << endl;

    cout << "性能测试开始" << endl;
    int n = 1000;
    int m = 500;
    cout << "n : " << n << endl;
    cout << "m : " << m << endl;
    long start = clock();
    int ans = ways3(n, m);
    long end = clock();
    cout << "取余之后的结果 : " << ans << endl;
    cout << "运行时间 : " << end - start << " 毫秒" << endl;
    cout << "性能测试结束" << endl;

    return 0;
}